package com.loriot.common.climbing_stairs_ii_3693;

public class Main {
    class Solution {
        public int climbStairs(int n, int[] costs) {
            // 局部
            int[] dp = new int[n+1];
            // 第0级台阶
            dp[0] = 0;
            // 第一级台阶一定只跳1次
            dp[1] = costs[0]+1;
            if(n==1)return dp[1];
            // 第2级台阶，由1级台阶或者0级台阶跳跃到的
            dp[2] = costs[1] + Math.min(dp[0]+4,dp[1]+1);
            for(int i=3;i<n+1;i++){
                dp[i] = costs[i-1] + Math.min(dp[i-1]+1,Math.min(dp[i-2]+4,dp[i-3]+9));
            }
            return dp[n];
        }
    }

    class Solution2 {
        public int climbStairs(int n, int[] costs) {
            // dp数组
            int[] dp = new int[n];
            // 第1级台阶
            dp[0] = costs[0]+1;
            // 如果只有1级
            if(n==1)return dp[0];
            // 第二级台阶
            dp[1] = costs[1]+ Math.min(4,dp[0]+1);
            // 如果只有两级
            if(n==2)return dp[1];
            // 第三级台阶
            dp[2] = costs[2] + Math.min(dp[1]+1,Math.min(dp[0]+4,9));
            for(int i=3;i<n;i++){
                dp[i] = costs[i] + Math.min(dp[i-1]+1,Math.min(dp[i-2]+4,dp[i-3]+9));
            }
            return dp[n-1];
        }
    }

    class Solution3 {
        public int climbStairs(int n, int[] costs) {
            // 第0级台阶
            int a = 0;
            // 第一级台阶一定只跳1次，并且
            int b = costs[0]+1;
            if(n==1)return b;
            // 第2级台阶
            int c = costs[1] + Math.min(a+4,b+1);
            for(int i=3;i<n+1;i++){
                // 暂时保留上一级的
                int k  = costs[i-1] + Math.min(c+1,Math.min(b+4,a+9));
                // 状态转移
                a = b;
                b = c;
                c = k;
            }
            return c;
        }
    }
}
